package com.hqq.search.symbol_table;

import com.hqq.search.KeyMap;

import java.util.Iterator;

/**
 * SequentialArraySymbolTableSearch
 * 基于无序数组实现的符号表
 * Created by heqianqian on 2017/8/5.
 */
public class SequentialArraySymbolTableSearch<K, V> implements KeyMap<K, V> {

    private static final int DEFAULT_CAPACITY = 10;

    private K[] keyArray;

    private V[] valueArray;

    private int size;

    public SequentialArraySymbolTableSearch() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public SequentialArraySymbolTableSearch(int capacity) {
        keyArray = (K[]) new Object[capacity];
        valueArray = (V[]) new Object[capacity];
    }

    @Override
    public void put(K key, V value) {
        ensureCapacity();
        keyArray[size] = key;
        valueArray[size] = value;
        this.size++;
    }


    /**
     * 检查键值对数组容量是否足够
     */
    @SuppressWarnings("unchecked")
    private void ensureCapacity() {
        if (size == keyArray.length) {
            K[] kTemp = (K[]) new Object[keyArray.length * 2];
            V[] vTemp = (V[]) new Object[valueArray.length * 2];
            System.arraycopy(keyArray, 0, kTemp, 0, keyArray.length);
            System.arraycopy(valueArray, 0, vTemp, 0, valueArray.length);
            keyArray = kTemp;
            valueArray = vTemp;
        }
    }

    @Override
    public V get(K key) {
        for (int i = 0; i < size; i++) {
            if (keyArray[i].equals(key)) {
                return valueArray[i];
            }
        }
        return null;//不存在返回null
    }

    @Override
    public void delete(K key) {
        int index = -1;
        for (int i = 0; i < keyArray.length; i++) {
            if (keyArray[i].equals(key)) {
                index = i;
            }
        }
        if (index != -1) {
            remove(index);
        }else{
            throw new IllegalStateException("要删除的键不存在");
        }
    }

    private void remove(int index) {
        for (int i = index; i < size - 1; i++) {
            keyArray[i] = keyArray[i + 1];
            valueArray[i] = valueArray[i + 1];
        }
        this.size--;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public Iterator<K> iterator() {
        return new ArraySTSearchIterator(this);
    }

    /**
     * 数组型符号表迭代器
     */
    private class ArraySTSearchIterator implements Iterator<K> {

        private SequentialArraySymbolTableSearch<K, V> table;

        private int index;

        public ArraySTSearchIterator(SequentialArraySymbolTableSearch<K, V> table) {
            this.table = table;
        }

        @Override
        public boolean hasNext() {
            return index != table.size();
        }

        @Override
        public K next() {
            return table.keyArray[index++];
        }
    }
}
